#include "HeapSort.h"
void HeapCreate(Heap* hp, HPDataType* a, int n)//初始化
{

    int *b =(int *)malloc(sizeof(int)*n);
    if(b==NULL)
        exit(-1);
    hp->_a=b;

    memcpy(hp->_a,a,n*sizeof (int));
    hp->_size=hp->_capacity=n;
    HeapSort(hp->_a,n);
}


void HeapPush(Heap* hp, HPDataType x)// 堆的插入
{
    assert(hp);
    if(hp->_size==hp->_capacity)//满了
    {
        HPDataType* ptr= realloc(hp->_a,sizeof(HPDataType)*(hp->_capacity*2));
        if(ptr==NULL)
            exit(-1);
        hp->_a=ptr;
        hp->_capacity*=2;
    }
     hp->_a[hp->_size]=x;
    int father=(hp->_size-1)/2;
    if(hp->_a[father]>hp->_a[hp->_size])
    {
       AdjustUp(hp->_a,hp->_size,hp->_size);
    }
    hp->_size++;
}

void HeapPop(Heap* hp)// 堆的删除
{
    assert(hp);
    assert(!HeapEmpty(hp));
    hp->_size--;
}


HPDataType HeapTop(Heap* hp)//堆顶元素
{
    assert(hp);
    assert(!HeapEmpty(hp));
    return hp->_a[0];
}
int HeapSize(Heap* hp)//堆里面元素
{
    return hp->_size;
}
int HeapEmpty(Heap* hp)//判空
{
    return hp->_size==0;
}
void HeapDestory(Heap* hp)// 堆的销毁
{
    free(hp->_a);
    hp->_capacity=0;
    hp->_size=0;
}
void Swap(int *dest,int* src)//交换
{
    int tmp =*dest;
    *dest=*src;
    *src= tmp;
}
void AdjustDown(int *arr,int tmp,int father)//👇调整，他的俩个儿子节点一定要是小堆or大堆
{
    int son= father*2+1;//右孩子
    while(son<tmp)
    {
        if(son+1<tmp&&arr[son+1]>arr[son])//找左右孩子中最小的那个,且可以这个节点只有一个孩子
        {
            ++son;
        }
        if(arr[son]>arr[father])
        {
            Swap(&arr[father],&arr[son]);
            father=son;
            son=father*2+1;
        }
        else
        {
            break;
        }

    }
}


void AdjustUp(int *arr,int tmp,int son)//👆调整
{
    int father= (son-2)/2;
    while(son>0)
    {
        if(arr[father]>arr[son])
        {
            Swap(&arr[father],&arr[son]);
            son=father;
            father=(son-1)/2;
        }
        else
        {
            break;
        }
    }

}
void HeapSort(int *a,int n)//堆排序
{
    for(int i=(n-1-1)/2;i>=0;--i)//建立大堆or下堆
    {
        AdjustDown(a,n,i);
    }

    int end=n-1;
    while(end>0)
    {
        Swap(&a[0],&a[end]);
        AdjustDown(a,end,0);
        end--;
    }

}